The current Advanced Marking Scheme (AMS) algorithm is a relatively efficient algorithm for tracing IP addresses of Distributed Denial of Service (DDoS) attackers. However, as using hash functions to achieve compression of edge address, the AMS algorithm has many defects such as high complexity, poor confidentiality and a high ratio of false positives. In order to improve the efficiency of AMS, the AMS algorithm based on multidimensional pseudo-random sequences was designed. On one hand, replacing original hash functions, an edge sampling matrix was constructed with a full hardware device in a router to achieve the compression coding of IP address. On the other hand, combined with the compressed code of edge address and the calculation process of edge weight in the victim's side, the output of DDoS attack path graph was realized. In the simulation experiments, the performance of the AMS algorithm based on multidimensional pseudo-random sequences is basically the same as the original algorithm, which can effectively reduce misjudgment and quickly judge forged paths. The experimental results show that the proposed algorithm has high security, fast computation and strong anti-attack ability.